{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost Tree From Leaf Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #dynamic-programming #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #动态规划 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mctFromLeafValues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #叶值的最小代价生成树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组&nbsp;<code>arr</code>，考虑所有满足以下条件的二叉树：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个节点都有 <code>0</code> 个或是 <code>2</code> 个子节点。</li>\n",
    "\t<li>数组&nbsp;<code>arr</code>&nbsp;中的值与树的中序遍历中每个叶节点的值一一对应。</li>\n",
    "\t<li>每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个&nbsp;32 位整数。</p>\n",
    "\n",
    "<p>如果一个节点有 0 个子节点，那么该节点为叶节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/10/tree1.jpg\" style=\"width: 500px; height: 169px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [6,2,4]\n",
    "<strong>输出：</strong>32\n",
    "<strong>解释：</strong>有两种可能的树，第一种的非叶节点的总和为 36 ，第二种非叶节点的总和为 32 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/10/tree2.jpg\" style=\"width: 224px; height: 145px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [4,11]\n",
    "<strong>输出：</strong>44\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= arr.length &lt;= 40</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 15</code></li>\n",
    "\t<li>答案保证是一个 32 位带符号整数，即小于&nbsp;<code>2<sup>31</sup></code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-tree-from-leaf-values](https://leetcode.cn/problems/minimum-cost-tree-from-leaf-values/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-tree-from-leaf-values](https://leetcode.cn/problems/minimum-cost-tree-from-leaf-values/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,2,4]', '[4,11]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for x in arr:\n",
    "            while stack and stack[-1] <= x:\n",
    "                y = stack.pop()\n",
    "                if not stack or stack[-1] > x:\n",
    "                    res += y * x\n",
    "                else:\n",
    "                    res += stack[-1] * y\n",
    "            stack.append(x)\n",
    "        while len(stack) >= 2:\n",
    "            x = stack.pop()\n",
    "            res += stack[-1] * x\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        while len(arr) > 1:\n",
    "            mn = inf\n",
    "            del_i = 0\n",
    "            for i in range(len(arr) - 1):\n",
    "                if max(arr[i], arr[i + 1]) < mn:\n",
    "                    mn = max(arr[i], arr[i + 1])\n",
    "                    del_i = i + 1 if arr[i] > arr[i + 1] else i\n",
    "            ans += mn * arr[del_i]\n",
    "            del arr[del_i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for x in arr:\n",
    "            while st and st[-1] <= x:\n",
    "                y = st.pop()\n",
    "                if not st or st[-1] > x:\n",
    "                    ans += y * x\n",
    "                else:\n",
    "                    ans += st[-1] * y\n",
    "            st.append(x)\n",
    "\n",
    "        while len(st) >= 2:\n",
    "            x = st.pop()\n",
    "            ans += st[-1] * x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        while len(arr) > 1:\n",
    "            res += min(map(lambda x: x[0]*x[1], pairwise(arr)))\n",
    "            rmidx = min([i for i in range(len(arr)-1)], key=list(map(lambda x: x[0]*x[1], pairwise(arr))).__getitem__)\n",
    "            arr.pop(rmidx if arr[rmidx] < arr[rmidx+1] else rmidx + 1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        stack = []\n",
    "        sum = 0\n",
    "        for x in arr:\n",
    "            while stack and x>stack[-1]:\n",
    "                y = stack.pop()\n",
    "                if not stack or stack[-1]>x:\n",
    "                    sum += y*x\n",
    "                else :\n",
    "                    sum += stack[-1]*y\n",
    "            stack.append(x)\n",
    "        while(len(stack)>=2):\n",
    "            x = stack.pop()\n",
    "            sum += x*stack[-1]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        total = len(arr)\n",
    "        max_num = [[0] * total for _ in range(total)]\n",
    "        dp = [[0] * total for _ in range(total)]\n",
    "        for i in range(total):\n",
    "            max_num[i][i] = arr[i]\n",
    "\n",
    "        for length in range(1, total):\n",
    "            for l in range(total-length):\n",
    "                r = l + length\n",
    "                max_num[l][r] = max(arr[r], max_num[l][r-1])\n",
    "                dp[l][r] = dp[l][l] + dp[l+1][r] + max_num[l][l]*max_num[l+1][r]\n",
    "                for m in range(l+1, r):\n",
    "                    dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + max_num[l][m]*max_num[m+1][r])\n",
    "\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for x in arr:\n",
    "            while stack and stack[-1] <= x:\n",
    "                y = stack.pop()\n",
    "                if not stack or  stack[-1] > x:\n",
    "                    res += x * y\n",
    "                else:\n",
    "                    res += stack[-1] * y\n",
    "        \n",
    "            stack.append(x)\n",
    "        while len(stack) >= 2:\n",
    "            x = stack.pop()\n",
    "            res += x * stack[-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        stack = [inf]\n",
    "        ans = 0\n",
    "        for n in arr:\n",
    "            while stack[-1] < n:\n",
    "                ans += stack.pop() * min(n, stack[-1])\n",
    "            stack.append(n)\n",
    "        while len(stack) > 2:\n",
    "            ans += stack.pop() * stack[-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf for i in range(n)] for j in range(n)]\n",
    "        mval = [[0 for i in range(n)] for j in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j-1, -1, -1):\n",
    "                mval[i][j] = max(arr[i], mval[i+1][j])\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + mval[i][k] * mval[k+1][j])\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        \n",
    "            n = len(arr)\n",
    "            f = [[inf for _ in range(n)] for j in range(n)]\n",
    "            mval = [[0 for _ in range(n)] for i in range(n)]\n",
    "            \n",
    "            for i in range(n-1,-1,-1):\n",
    "                mval[i][i] = arr[i];f[i][i] = 0\n",
    "                for j in range(i+1,n):\n",
    "                    mval[i][j] = max(arr[j],mval[i][j-1])\n",
    "                    for k in range(i,j):\n",
    "                        f[i][j] = min(f[i][j],f[i][k] + f[k+1][j] + mval[i][k] * mval[k+1][j])\n",
    "            \n",
    "            return f[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        total = len(arr)\n",
    "        max_num = [[0] * total for _ in range(total)]\n",
    "        dp = [[0] * total for _ in range(total)]\n",
    "        for i in range(total):\n",
    "            max_num[i][i] = arr[i]\n",
    "\n",
    "        for length in range(1, total):\n",
    "            for l in range(total-length):\n",
    "                r = l + length\n",
    "                max_num[l][r] = max(arr[r], max_num[l][r-1])\n",
    "                dp[l][r] = dp[l][l] + dp[l+1][r] + max_num[l][l]*max_num[l+1][r]\n",
    "                for m in range(l+1, r):\n",
    "                    dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + max_num[l][m]*max_num[m+1][r])\n",
    "\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        sum = 0\n",
    "        while len(arr) > 1:\n",
    "            i = arr.index(min(arr))\n",
    "            sum += min(arr[i-1:i]+arr[i+1:i+2]) * arr.pop(i)\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            g[i][i] = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = max(g[i][j - 1], arr[j])\n",
    "                f[i][j] = min(f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j] for k in range(i, j))\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            g[i][i] = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = max(g[i][j - 1], arr[j])\n",
    "                f[i][j] = min(f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j] for k in range(i, j))\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            g[i][i] = arr[i]\n",
    "            \n",
    "            for j in range(i+1, n):\n",
    "                g[i][j] = max(g[i][j-1], arr[j])\n",
    "                \n",
    "                f[i][j] = min(f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j] for k in range(i, j))\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf for i in range(n)] for j in range(n)]\n",
    "        mval = [[0 for i in range(n)] for j in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                mval[i][j] = max(arr[i], mval[i + 1][j])\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mval[i][k] * mval[k + 1][j])\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf for i in range(n)] for j in range(n)]\n",
    "        mval = [[0 for i in range(n)] for j in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j-1,-1,-1):\n",
    "                mval[i][j] = max(arr[i],mval[i+1][j])\n",
    "                for k in range(i,j):\n",
    "                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+mval[i][k]*mval[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        while len(arr) > 1:\n",
    "            min_val = min(arr)\n",
    "            idx = arr.index(min_val)\n",
    "            if idx > 0 and idx < len(arr) - 1: #有左有右\n",
    "                left_val, right_val = arr[idx - 1], arr[idx + 1]\n",
    "            elif idx == len(arr) - 1: #有左没右\n",
    "                left_val, right_val = arr[idx - 1], 16 #为什么是16？因为最大只有15\n",
    "            elif idx == 0: #有右没左\n",
    "                left_val, right_val = 16, arr[idx + 1]\n",
    "                \n",
    "            res += min(min_val * left_val, min_val * right_val)\n",
    "            arr.remove(min_val) #把当前最小值删掉，已经用完了\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        result = []\n",
    "        for i in range(len(arr) - 1):\n",
    "            min_value = min(arr)\n",
    "            min_index = arr.index(min_value)\n",
    "            if 0 < min_index < len(arr) - 1:\n",
    "                max_value = arr[min_index + 1] if arr[min_index + 1] < arr[min_index - 1] else arr[min_index - 1]\n",
    "            elif min_index == 0:\n",
    "                max_value = arr[min_index + 1]\n",
    "            else:\n",
    "                max_value = arr[min_index - 1]\n",
    "            result.append(min_value * max_value)\n",
    "            arr.remove(min_value)\n",
    "        return sum(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心\n",
    "    def mctFromLeafValues1(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        while len(arr) > 1:\n",
    "            n = len(arr)\n",
    "            pre = float(\"inf\")\n",
    "            j = -1\n",
    "            for i in range(n-1):\n",
    "                if arr[i]*arr[i+1] < pre:\n",
    "                    j = i\n",
    "                    pre = arr[i]*arr[i+1]\n",
    "\n",
    "            ans += arr[j]*arr[j+1]\n",
    "            if arr[j] < arr[j+1]:\n",
    "                arr.pop(j)\n",
    "            else:\n",
    "                arr.pop(j+1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 单调栈\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        stack = [float('inf')]\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            while stack and stack[-1] <= num:\n",
    "                cur = stack.pop(-1)\n",
    "                res += min(stack[-1]*cur, cur*num)\n",
    "\n",
    "            stack.append(num)\n",
    "\n",
    "        m = len(stack)\n",
    "        for i in range(m-2, 0, -1):\n",
    "            res += stack[i]*stack[i+1]\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf for i in range(n)] for j in range(n)]\n",
    "        mval = [[0 for i in range(n)] for j in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                mval[i][j] = max(arr[i], mval[i + 1][j])\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mval[i][k] * mval[k + 1][j])\n",
    "        return dp[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        while len(arr) > 1:\n",
    "            minLeft = 0\n",
    "            minProd = 2e32\n",
    "            # select smallest product neighbor\n",
    "            for i in range(len(arr) - 1):\n",
    "                prod = arr[i] * arr[i + 1]\n",
    "                if prod < minProd:\n",
    "                    minProd = prod\n",
    "                    minLeft = i\n",
    "            \n",
    "            # remove this neighbor and insert back the prod\n",
    "            ans += minProd\n",
    "            if arr[minLeft] < arr[minLeft + 1]:\n",
    "                arr.pop(minLeft)\n",
    "            else:\n",
    "                arr.pop(minLeft + 1)\n",
    "            \n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        sum = 0\n",
    "        while len(arr) > 1:\n",
    "            idx = -1\n",
    "            m = 2147483647\n",
    "            for i in range(1, len(arr)):\n",
    "                if arr[i] * arr[i - 1] < m:\n",
    "                    idx = i - 1\n",
    "                    m = arr[i] * arr[i - 1]\n",
    "            arr = arr[:idx] + [max(arr[idx], arr[idx + 1])] + arr[idx + 2:]\n",
    "            print(arr)\n",
    "            sum += m\n",
    "        return sum\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        maxVal = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            maxVal[i][i] = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                maxVal[i][j] = max(maxVal[i][j - 1], arr[j])\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = float('inf')\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(\n",
    "                        dp[i][j],\n",
    "                        dp[i][k] + dp[k + 1][j] + maxVal[i][k] * maxVal[k + 1][j]\n",
    "                    )\n",
    "                    \n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for x in arr:\n",
    "            while stack and stack[-1] <= x:\n",
    "\n",
    "                y = stack.pop()\n",
    "\n",
    "                if not stack or stack[-1] > x:\n",
    "                    res += y * x\n",
    "\n",
    "                else:\n",
    "                    res += stack[-1] * y\n",
    "            \n",
    "            stack.append(x)\n",
    "\n",
    "        while len(stack) >= 2:\n",
    "\n",
    "            x = stack.pop()\n",
    "\n",
    "            res += stack[-1] * x\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        total = len(arr)\n",
    "        max_num = [[0] * total for _ in range(total)]\n",
    "        dp = [[0] * total for _ in range(total)]\n",
    "\n",
    "        for length in range(total):\n",
    "            for l in range(total-length):\n",
    "                r = l + length\n",
    "                if l == r:\n",
    "                    max_num[l][r] = arr[l]\n",
    "                else:\n",
    "                    max_num[l][r] = max(arr[r], max_num[l][r-1])\n",
    "                    for m in range(l, r):\n",
    "                        if dp[l][r] == 0:\n",
    "                            dp[l][r] = dp[l][m] + dp[m+1][r] + max_num[l][m]*max_num[m+1][r]\n",
    "                        else:\n",
    "                            dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + max_num[l][m]*max_num[m+1][r])\n",
    "\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1130 lang=python\n",
    "#\n",
    "# [1130] 叶值的最小代价生成树\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def mctFromLeafValues(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n =len(arr)\n",
    "        dp = [[999999999] * len(arr) for i in range(len(arr))]\n",
    "        mval = [[0 for i in range(n)] for j in range(n)]\n",
    "        for i in range(len(arr)):\n",
    "            dp[i][i] = 0\n",
    "            mval[i][i] = 0\n",
    "        for i in range(len(arr)-1):\n",
    "            dp[i][i+1] = arr[i] * arr[i + 1]\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i,len(arr)):\n",
    "                mval[i][j] = max(mval[i][j-1],arr[j])\n",
    "        for k in range(2,len(arr)):\n",
    "            for begin in range(len(arr)-k):\n",
    "                for mid in range(begin,begin+k):\n",
    "                    add_val = mval[begin][mid] * mval[mid + 1][begin + k]\n",
    "                    dp[begin][begin + k] = min(dp[begin][mid] + dp[mid + 1][begin + k] + add_val, dp[begin][begin + k])\n",
    "        return dp[0][len(arr) - 1]\n",
    "# @lc code=end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for num in arr:\n",
    "            lst = []\n",
    "            while stack and stack[-1] < num:\n",
    "                x = stack.pop()\n",
    "                lst.append(x)\n",
    "            if lst:\n",
    "                n = len(lst)\n",
    "                for i in range(n - 1):\n",
    "                    ans += lst[i] * lst[i + 1]\n",
    "                ans += lst[-1]*num\n",
    "            stack.append(num)\n",
    "\n",
    "        n = len(stack)\n",
    "        for i in range(n-1):\n",
    "            ans += stack[i]*stack[i+1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        stack = []\n",
    "\n",
    "\n",
    "        for x in arr:\n",
    "\n",
    "\n",
    "            while stack and stack[-1] <= x:\n",
    "\n",
    "\n",
    "                y = stack.pop()\n",
    "\n",
    "                if not stack or stack[-1] > x:\n",
    "                    res += y * x\n",
    "\n",
    "                else:\n",
    "\n",
    "                    res += stack[-1] * y\n",
    "\n",
    "            stack.append(x)\n",
    "\n",
    "    \n",
    "        while len(stack) >= 2:\n",
    "            x = stack.pop()\n",
    "            res += stack[-1] * x\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        total = len(arr)\n",
    "        max_num = [[0] * total for _ in range(total)]\n",
    "        dp = [[0] * total for _ in range(total)]\n",
    "\n",
    "        for length in range(total):\n",
    "            for l in range(total-length):\n",
    "                r = l + length\n",
    "                if l == r:\n",
    "                    max_num[l][r] = arr[l]\n",
    "                else:\n",
    "                    max_num[l][r] = max(arr[r], max_num[l][r-1])\n",
    "                    for m in range(l, r):\n",
    "                        if dp[l][r] == 0:\n",
    "                            dp[l][r] = dp[l][m] + dp[m+1][r] + max_num[l][m]*max_num[m+1][r]\n",
    "                        else:\n",
    "                            dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + max_num[l][m]*max_num[m+1][r])\n",
    "\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf for i in range(n)] for j in range(n)]\n",
    "        mval = [[0 for i in range(n)] for j in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                mval[i][j] = max(arr[i], mval[i + 1][j])\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + mval[i][k] * mval[k+1][j])\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        sum_ = self.cat(arr, 0)\n",
    "        return sum_\n",
    "    def cat(self, arr, sum_):\n",
    "        min_ = 99999\n",
    "        idx = -1\n",
    "        if len(arr) == 1:\n",
    "            return sum_\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]<min_:\n",
    "                min_ = arr[i]\n",
    "                idx = i\n",
    "        if idx == 0:\n",
    "            s = self.cat(arr[1:], sum_ + arr[0] * arr[1])\n",
    "        elif idx == len(arr)-1:\n",
    "            s = self.cat(arr[:-1], sum_ + arr[-2] * arr[-1])\n",
    "        else:\n",
    "            if arr[idx-1]>arr[idx+1]:\n",
    "                s = self.cat(arr[:idx]+arr[idx+1:], sum_ + arr[idx] * arr[idx+1])\n",
    "            else:\n",
    "                s = self.cat(arr[:idx] + arr[idx+1:], sum_ + arr[idx] * arr[idx - 1])\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[2**31] * n for _ in range(n)]\n",
    "        for l in range(1,n+1):\n",
    "            for i in range(n-l+1):\n",
    "                if l == 1: dp[i][i] = 0\n",
    "                else:\n",
    "                    for k in range(i,i+l-1):#左子数最右侧叶子节点的下标\n",
    "                        dp[i][i+l-1] = min(dp[i][i+l-1],dp[i][k] + dp[k+1][i+l-1] \\\n",
    "                        + max(arr[i:k+1])*max(arr[k+1:i+l]))\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for x in arr:\n",
    "            while stack and stack[-1] <= x:\n",
    "                y = stack.pop()\n",
    "                if not stack or stack[-1] > x:\n",
    "                    res += y * x\n",
    "                else:\n",
    "                    res += stack[-1] * y\n",
    "            stack.append(x)\n",
    "        while len(stack) >= 2:\n",
    "            x = stack.pop()\n",
    "            res += stack[-1] * x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        stack = [float('inf')]\n",
    "        for a in arr:\n",
    "            while stack and stack[-1]<=a:\n",
    "                p = stack.pop()\n",
    "                res += min(stack[-1],a)*p\n",
    "            stack.append(a)\n",
    "        while len(stack)>2:\n",
    "            res += stack.pop()*stack[-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "        g = [[0]*n for _ in range(n)]\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            g[i][i] = arr[i]\n",
    "            \n",
    "            for j in range(i+1, n):\n",
    "                g[i][j] = max(g[i][j-1], arr[j])\n",
    "                \n",
    "                #\"子树1\"的非叶子节点和 + “子树2”的非叶子节点和 + 根节点值\n",
    "                f[i][j] = min(f[i][k] + f[k + 1][j] +\\\n",
    "                    g[i][k] * g[k + 1][j] for k in range(i, j))\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            g[i][i] = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = max(g[i][j - 1], arr[j])\n",
    "                f[i][j] = min(f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j] for k in range(i, j))\n",
    "        return f[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            g[i][i] = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = max(g[i][j - 1], arr[j])\n",
    "                f[i][j] = min(f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j] for k in range(i, j))\n",
    "        return f[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        stack = [float('inf')]\n",
    "        # stack = [arr[0]]\n",
    "        n = len(arr)\n",
    "        result = 0 \n",
    "        for i in range(n):\n",
    "            while len(stack) > 0 and arr[i] > stack[-1]:\n",
    "                result += stack.pop() * min(stack[-1], arr[i])\n",
    "            stack.append(arr[i])\n",
    "        while len(stack) > 2:\n",
    "            result += stack.pop() * stack[-1]\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf for __ in range(n)] for _ in range(n)]\n",
    "        mval = [[0 for __ in range(n)] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                mval[i][j] = max(arr[i], mval[i + 1][j])\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mval[i][k] * mval[k + 1][j])\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf for i in range(n)] for j in range(n)]\n",
    "        mval = [[0 for i in range(n)] for j in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j - 1, -1, -1):\n",
    "                mval[i][j] = max(arr[i], mval[i + 1][j])\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mval[i][k] * mval[k + 1][j])\n",
    "        return dp[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[inf]*n for _ in range(n)]\n",
    "        mval = [[0]*n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            mval[j][j] = arr[j]\n",
    "            dp[j][j] = 0\n",
    "            for i in range(j-1,-1,-1):\n",
    "                mval[i][j] = max(arr[i],mval[i+1][j])\n",
    "                for k in range(i,j):\n",
    "                    dp[i][j] = min(dp[i][j],dp[k+1][j]+mval[i][k]*mval[k+1][j]+dp[i][k])\n",
    "\n",
    "\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        arr = [0] + arr\n",
    "        maxarr = [[0] * len(arr) for _ in arr]\n",
    "        for i in range(1, len(arr)):\n",
    "            maxarr[i][i] = arr[i]\n",
    "        dp = [[float('inf')] * len(arr) for _ in arr]\n",
    "        for i in range(len(arr)):\n",
    "            dp[i][i] = 0\n",
    "        for l in range(2, len(arr)):\n",
    "            for i in range(1, len(arr)-l+1):\n",
    "                j = i + l - 1\n",
    "                if maxarr[i][j-1] > arr[j]:\n",
    "                    maxarr[i][j] = maxarr[i][j-1]\n",
    "                else:\n",
    "                    maxarr[i][j] = arr[j]\n",
    "                for k in range(i, j):\n",
    "                    if dp[i][j] > dp[i][k] + dp[k+1][j] + maxarr[i][k]*maxarr[k+1][j]:\n",
    "                        dp[i][j] = dp[i][k] + dp[k+1][j] + maxarr[i][k]*maxarr[k+1][j]\n",
    "        return dp[1][-1]\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        max_matrix=[[0]*n for _ in range(n)]\n",
    "       \n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                max_matrix[i][j]=max(arr[i:j+1])\n",
    "        print(max_matrix)\n",
    "        for i in range(n):\n",
    "            dp[i][i]=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(i+1,j+1):\n",
    "                    dp[i][j]=min(dp[i][k-1]+dp[k][j]+max_matrix[i][k-1]*max_matrix[k][j],dp[i][j])\n",
    "        print(dp)\n",
    "        return dp[0][n-1]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[[inf]*n for _ in range(n)]\n",
    "        max_matrix=[[0]*n for _ in range(n)]\n",
    "       \n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                max_matrix[i][j]=max(arr[i:j+1])\n",
    "        print(max_matrix)\n",
    "        for i in range(n):\n",
    "            dp[i][i]=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(i+1,j+1):\n",
    "                    dp[i][j]=min(dp[i][k-1]+dp[k][j]+max_matrix[i][k-1]*max_matrix[k][j],dp[i][j])\n",
    "        print(dp)\n",
    "        return dp[0][n-1]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1130 lang=python\n",
    "#\n",
    "# [1130] 叶值的最小代价生成树\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def mctFromLeafValues(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [[999999999] * len(arr) for i in range(len(arr))]\n",
    "        for i in range(len(arr)):\n",
    "            dp[i][i] = 0\n",
    "        for i in range(len(arr)-1):\n",
    "            dp[i][i+1] = arr[i] * arr[i + 1]\n",
    "        \n",
    "        for k in range(2,len(arr)):\n",
    "            for begin in range(len(arr)-k):\n",
    "                print(k,begin)\n",
    "                for mid in range(begin,begin+k):\n",
    "                    add_val = max(arr[begin:mid + 1]) * max(arr[(mid + 1):(begin + k + 1)]) \n",
    "                    dp[begin][begin + k] = min(dp[begin][mid] + dp[mid + 1][begin + k] + add_val, dp[begin][begin + k])\n",
    "        return dp[0][len(arr) - 1]\n",
    "# @lc code=end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        '''\n",
    "       a*b+(a*b*c)\n",
    "\n",
    "       a*b*c+b*c\n",
    "\n",
    "       \n",
    "        '''\n",
    "        dp = [[0 for _ in arr] for _ in arr]\n",
    "        max_dp = [[0 for _ in arr] for _ in arr]\n",
    "\n",
    "        def find_max(i, j):\n",
    "            if max_dp[i][j] != 0:\n",
    "                return max_dp[i][j]\n",
    "            if i == j:\n",
    "                max_dp[i][j] = arr[i]\n",
    "            else:\n",
    "                max_dp[i][j] = max(arr[i], find_max(i + 1, j))\n",
    "            # print(f\"max_dp[{i}][{j}]= {max_dp[i][j]}\")\n",
    "            return max_dp[i][j]\n",
    "\n",
    "        def calculate(i, j, deep):\n",
    "            if dp[i][j] != 0:\n",
    "                return dp[i][j]\n",
    "\n",
    "            if i == j:\n",
    "                dp[i][j] = 0\n",
    "            elif i + 1 == j:\n",
    "                dp[i][j] = arr[i] * arr[j]\n",
    "            else:\n",
    "                min_list = []\n",
    "                # print(f\"{'*' * deep} dp[{i}][{j}]\")\n",
    "                for cur_index in range(i, j):\n",
    "                    cur_min = calculate(i, cur_index, deep + 1) + calculate(cur_index+1, j, deep + 1) + \\\n",
    "                              find_max(i,cur_index) * find_max(cur_index+1, j)\n",
    "                    min_list.append(cur_min)\n",
    "                dp[i][j] = min(min_list)\n",
    "            # print(f\"{' ' * deep} dp[{i}][{j}]= {dp[i][j]} \")\n",
    "            return dp[i][j]\n",
    "\n",
    "        result = calculate(0, len(arr) - 1, 0)\n",
    "        # print(dp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dp(i,j):\n",
    "            if(j == i):\n",
    "                return 0\n",
    "            if(j - i == 1):\n",
    "                return arr[i]*arr[j]\n",
    "            res = float('inf')\n",
    "            for k in range(i,j):\n",
    "                res = min(res, dp(i,k) + dp(k+1,j) + max(arr[i:k+1])*max(arr[k+1:j+1]))\n",
    "            return res\n",
    "        return dp(0,len(arr)-1)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(l,r):\n",
    "            #print(l,r)\n",
    "            if l+1==r:return 0\n",
    "            ans=inf\n",
    "            for i in range(l+1,r):\n",
    "                #print(i,l,r,max(arr[l:i]),max(arr[i:r]))\n",
    "                ans=min(ans,max(arr[l:i])*max(arr[i:r])+dfs(l,i)+dfs(i,r))\n",
    "            return ans\n",
    "        return dfs(0,len(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        \n",
    "        n = len(arr)\n",
    "        if n==2: return arr[0]*arr[1]\n",
    "\n",
    "        rec = [[-1]*n for _ in range(n)]\n",
    "        def travel(l,r)->int:\n",
    "            if l==r: return 0\n",
    "            if l==r-1: return arr[l]*arr[r]\n",
    "            if rec[l][r]!=-1:\n",
    "                return rec[l][r]\n",
    "\n",
    "            res = float('inf')\n",
    "            for i in range(l,r):\n",
    "                left = travel(l, i)\n",
    "                right = travel(i+1, r)\n",
    "                cur = left+right+max(arr[l:i+1])*max(arr[i+1:r+1])\n",
    "                res = min(res, cur)\n",
    "            rec[l][r] = res\n",
    "            return res\n",
    "        \n",
    "        return travel(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(l,r):\n",
    "            #print(l,r)\n",
    "            if l+1==r:return 0\n",
    "            ans=inf\n",
    "            mx=arr[l]\n",
    "            for i in range(l+1,r):\n",
    "                #print(i,l,r,max(arr[l:i]),max(arr[i:r]))\n",
    "                ans=min(ans,mx*max(arr[i:r])+dfs(l,i)+dfs(i,r))\n",
    "                mx=max(mx,arr[i])\n",
    "            return ans\n",
    "        return dfs(0,len(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(l,r):\n",
    "            if l+1==r:return 0\n",
    "            ans=inf\n",
    "            mx=arr[l]\n",
    "            for i in range(l+1,r):\n",
    "                ans=min(ans,mx*max(arr[i:r])+dfs(l,i)+dfs(i,r))\n",
    "                mx=max(mx,arr[i])\n",
    "            return ans\n",
    "        return dfs(0,len(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def count(i: int, j: int):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i, j):\n",
    "                res = min(res, max(arr[i:k+1]) * max(arr[k+1:j+1]) + count(i, k) + count(k+1, j))\n",
    "            return res\n",
    "\n",
    "        return count(0, len(arr)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        memo = {}\n",
    "        # 根据题目描述，数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应，我们可以将数组划分为左右两个非空子数组，分别对应树的左右子树，递归地求解每个子树的所有非叶节点的值的最小可能总和。\n",
    "        def dfs(i, j): # 表示数组 arr 中下标范围[i,j] 内的所有非叶节点的值的最小可能总和\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i >= j: # J=j只有一个元素，没有非叶节点\n",
    "                return 0\n",
    "\n",
    "            res = float('inf')\n",
    "            for k in range(i, j):\n",
    "                # [i...k] vs [k+1...j]\n",
    "                cost = max(arr[i: k + 1]) * max(arr[k + 1: j + 1]) # cost is root val\n",
    "                res = min(res, cost + dfs(i, k) + dfs(k + 1, j))\n",
    "            memo[(i, j)] = res\n",
    "            return memo[(i, j)]\n",
    "        return dfs(0, len(arr) -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dp(i,j):\n",
    "            if(j == i):\n",
    "                return 0\n",
    "            if(j - i == 1):\n",
    "                return arr[i]*arr[j]\n",
    "            res = float('inf')\n",
    "            for k in range(i,j):\n",
    "                res = min(res, dp(i,k) + dp(k+1,j) + max(arr[i:k+1])*max(arr[k+1:j+1]))\n",
    "            return res\n",
    "        return dp(0,len(arr)-1)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            return min(dfs(i, k) + dfs(k + 1, j) + g[i][k] * g[k + 1][j] for k in range(i, j))\n",
    "\n",
    "        n = len(arr)\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            g[i][i] = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = max(g[i][j - 1], arr[j])\n",
    "        \n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        # 可以预处理得到arr[i:j]的最大值\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            # 如果是叶子结点\n",
    "            if i==j:\n",
    "                return 0 \n",
    "            res=inf\n",
    "            for k in range(i,j):\n",
    "                res=min(res,dfs(i,k)+dfs(k+1,j)+g[i][k]*g[k+1][j])\n",
    "            return res \n",
    "        # g[i][j]表示arr【i]到arr【j】的最大值\n",
    "        n=len(arr)      \n",
    "        g=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            g[i][i]=arr[i]\n",
    "            for j in range(i+1,n):\n",
    "                g[i][j]=max(g[i][j-1],arr[j]) \n",
    "        return dfs(0,n-1)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "\n",
    "            if(i==j-1):\n",
    "                return arr[i] * arr[j]\n",
    "            if(i==j):\n",
    "                return 0\n",
    "\n",
    "            ans = float(\"inf\")\n",
    "            for k in range(i,j):\n",
    "                left = max(arr[i:k+1])\n",
    "                right = max(arr[k+1:j+1])\n",
    "                ans = min(dfs(i,k)+dfs(k+1,j)+left*right, ans)\n",
    "            print(i,j, ans)\n",
    "            return ans\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> (int, int):\n",
    "            if i == j:\n",
    "                return (0, arr[i])\n",
    "            res = inf\n",
    "            mx = max(arr[i:j + 1])\n",
    "            for k in range(i,j):\n",
    "                lv, lmx = dfs(i, k)\n",
    "                rv, rmx = dfs(k + 1, j)\n",
    "                res = min(res, lv + rv + lmx * rmx)\n",
    "            return (res, mx)\n",
    "        return dfs(0, n - 1)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def dfs(numbers):\n",
    "            if len(numbers) <= 1:\n",
    "                return 0\n",
    "\n",
    "            key = tuple(numbers)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "\n",
    "            result = []\n",
    "            for i in range(len(numbers) - 1):\n",
    "                left_arr = numbers[:i+1]\n",
    "                right_arr = numbers[i+1:]\n",
    "                currnet = max(left_arr) * max(right_arr)\n",
    "\n",
    "                left = dfs(left_arr)\n",
    "                right = dfs(right_arr)\n",
    "\n",
    "                result.append(currnet + left + right)\n",
    "\n",
    "            memo[key] = min(result)\n",
    "            return memo[key]\n",
    "\n",
    "        return dfs(arr)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def bt(i, j):\n",
    "            if i == j:\n",
    "                return arr[i], 0\n",
    "            else:\n",
    "                min_s = inf\n",
    "                max_v = -inf\n",
    "                for k in range(i, j):\n",
    "                    l_max, l_sum = bt(i, k)\n",
    "                    r_max, r_sum = bt(k + 1, j)\n",
    "                    max_v = max(max_v, l_max, r_max)\n",
    "                    min_s = min(min_s, l_sum + r_sum + l_max * r_max)\n",
    "                return max_v, min_s\n",
    "        return bt(0, len(arr) - 1)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\r\n",
    "        # 区间dp \r\n",
    "        @ cache \r\n",
    "        def dfs(i: int, j: int) -> (int, int):\r\n",
    "            if i == j:\r\n",
    "                return  0, arr[i] \r\n",
    "            # 枚举划分中点 \r\n",
    "            s = inf \r\n",
    "            for k in range(i, j):\r\n",
    "                ls, lmx = dfs(i, k)\r\n",
    "                rs, rmx = dfs(k + 1, j)\r\n",
    "                s = min(s, ls + rs + lmx * rmx)\r\n",
    "            return s, max(lmx, rmx)\r\n",
    "        return dfs(0, len(arr) - 1)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return arr[i], arr[i]\n",
    "            elif i + 1 == j:\n",
    "                return max(arr[i], arr[j]), arr[i] + arr[j] + arr[i] * arr[j]\n",
    "\n",
    "            res = [0, float('inf')]\n",
    "            for k in range(i, j):\n",
    "                l, r = dfs(i, k), dfs(k + 1, j)\n",
    "                if (total := l[1] + r[1] + l[0] * r[0]) < res[1]:\n",
    "                    res = [max(l[0], r[0]), total]\n",
    "            return res\n",
    "\n",
    "        return dfs(0, len(arr) - 1)[1] - sum(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mctFromLeafValues(self, arr: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return arr[i], arr[i]\n",
    "            elif i + 1 == j:\n",
    "                return max(arr[i], arr[j]), arr[i] + arr[j] + arr[i]* arr[j]\n",
    "\n",
    "            res = [0, float('inf')]\n",
    "            for k in range(i, j):\n",
    "                l, r = dfs(i, k), dfs(k + 1, j)\n",
    "                if (total := l[1] + r[1] + l[0]* r[0]) < res[1]:\n",
    "                    res = [max(l[0], r[0]), total]\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        return dfs(0, len(arr) - 1)[1] - sum(arr)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
